package reback;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class item22 {
}
class Solution {
    public static List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList();
        backtrack(ans, "", 0, 0, n);
        return ans;
    }

    public static void backtrack(List<String> ans, String cur, int open, int close, int max){
        if (cur.length() == max * 2) {
            ans.add(cur);
            return;
        }
        //当左括号个数小于n的时候进行
        if (open < max) {
            backtrack(ans, cur+"(", open+1, close, max);
            System.out.println(cur);
        }
        //当右括号小于左括号的时候
        if (close < open){
            backtrack(ans, cur+")", open, close+1, max);
        }

    }
    public static void main(String[] args){
        List<String> list = generateParenthesis(3);
        Iterator<String> iterator = list.iterator();
        while(iterator.hasNext()){
            System.out.println(iterator.next());
        }
    }

}